//
// Created by Administrator on 2021/6/10.
//

//给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
//
//你可以认为每种硬币的数量是无限的。
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/coin-change
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    int coinChange(vector<int> &coins, int amount) {
        if (amount == 0) return 0;
        vector<int> dp(amount + 1, 10e4);
        dp[0] = 0;
        for (auto &val : coins) { // 遍历硬币面额
            for (int i = 1; i <= amount; ++i) { // 遍历目标面额
                if (val <= i) {
                    dp[i] = min(dp[i - val] + 1, dp[i]);
                }
            }
        }
        return dp.back() == 10e4 ? -1 : dp.back();
    }
};

int main() {
    vector<int> coins{1, 2, 5};
    Solution sol;
    cout << sol.coinChange(coins, 11) << endl;
    return 0;
}